\documentclass[10pt,a4paper,titlepage,oneside]{article}
\usepackage[top=2.5cm, bottom=2cm, left=2.5cm, right=1cm]{geometry} 
% Font, accents
\usepackage[utf8]{inputenc}
\usepackage{fancyhdr}
\usepackage[T1]{fontenc}

% Interactive index
\usepackage{hyperref}
% Spanish titles
\usepackage[spanish]{babel}
% Attached files
\usepackage{attachfile}
\attachfilesetup{
  icon = Paperclip
}
% Fix curly verbatim apostrophes
\usepackage{upquote,textcomp}
% Make lists without bullets
\renewenvironment{itemize}{
 \begin{list}{}{
  \setlength{\leftmargin}{1.5em}
 }
}{
 \end{list}
}




%Customize things
\usepackage[margin=0pt,font=small,labelfont=bf]{caption}
\usepackage{graphicx}
\usepackage[usenames,dvipsnames]{xcolor}

% Sections and subsections colors
\usepackage{titlesec}
\titleformat{\section}
{\color{Blue}\normalfont\Large\bfseries}
{\color{Blue}\thesection}{1em}{}
\newcommand{\sectionbreak}{\clearpage}


% Document properties
\title{\textbf{Trabajo Práctico: Indexador de Textos}\linebreak
\\Entrega de diseño}
\author{Federico Farina \texttt{<federicofarina22{@}gmail.com>}\\
Nicolás Vazquez \texttt{<nickva1988@gmail.com>}\\
\\
\normalsize{1er. Cuatrimestre de 2013} \\
\normalsize{75.06 Organización de Datos} \\
\normalsize{Facultad de Ingeniería, Universidad de Buenos Aires}\\} 

\date{\today}
\hypersetup{
  colorlinks = true,
  urlcolor=blue,
  pdflang = es,
  pdfauthor = {Federico Farina},
  pdfproducer = {Federico Farina},
  pdfcreator = Texmaker,
  pdftitle = {Informe de Organización de datos: Entrega de diseño},
  pdfsubject = {},
  pdfpagemode = UseNone
}
\begin{document}
   % code start
    \fancyhead[LE]{\leftmark} 
    \fancyhead[RO]{\rightmark} 
    \fancyhead[L]{Organización de datos 75.06}
    \fancyhead[R]{Entrega de diseño}    
    \renewcommand{\headrulewidth}{0.4pt} 
    \renewcommand{\footrulewidth}{0pt}
    % code end

    % set pagestyle to use fancy header and footer
    \pagestyle{fancy}


 \maketitle
  \setcounter{page}{1}
  \pagenumbering{roman}
  \tableofcontents

\newpage{}
\pagenumbering{arabic}
\setcounter{page}{1}

\section{Registro de repositorios y documentos a indexar}

En esta etapa se procederá a registrar el repositorio y los documentos que se van indexando.


\subsection{Identificación de los documentos a indexar}

Como primera medida, se les asignará un identificador. Sin esto sería imposible devolver documentos como resultados, ya que se perdería la referencia a los mismos. 
\\Para almacenar la información relativa a los distintos documentos que se van indexando se creará un archivo indexado con registros de longitud variable, con el objetivo de poder realizar una búsqueda por clave en la etapa de consultas. En este caso, la clave de búsqueda será el número de documento.\\
\\Los registros tendrán el siguiente formato:


\begin{table}[h]
\centering
% centering table
\begin{tabular}{| c | c |}
\hline
NumBytes & Path raíz\\
\hline
uint8\_t & string\\
\hline
% inserts single-line
\end{tabular}
\caption {Header del archivo de documentos}
\end{table}


\begin{table}[h]
\centering
% centering table
\begin{tabular}{| c | c | c |}
\hline
NroDOC & NumBytes II & Path restante\\
\hline
uint32\_t & uint8\_t & string\\
\hline
% inserts single-line
\end{tabular}
\caption {Cuerpo del archivo de documentos}
\end{table}

El header solo se escribirá una vez al comienzo del mismo. El resto de los campos conforman un registro X.\\
El campo NumBytes indica cuántos caracteres se deben leer para formar el string que se encuentra en el campo contiguo; Path Restante concatenado al Path Raíz conforma el path absoluto del archivo y NroDOC es el identificador que se le asignará a cada documento, por orden de procesamiento.\\
\\
El índice será un archivo con registros de longitud fija, con el objetivo de poder obtener el offset al archivo anterior en un solo acceso por referencia por número de celda, la cual coincidirá con el número de documento, dado que naturalmente se encuentra ordenado por éste último. De ésta manera no se necesitará realizar una búsqueda binaria.\\ 
\\El formato del índice será el siguiente:

\begin{table}[h]
\centering
% centering table
\begin{tabular}{| c | c |}
\hline
NroDOC&Offset\\
\hline
uint32\_t & uint32\_t\\
\hline
\end{tabular}
\end{table}

Donde NroDOC servirá de clave para relacionar ambos archivos y el siguiente campo es el offset al registro buscado en el archivo anterior.
\newpage
\subsection{Identificación de los diferentes repositorios}
Para la identificación de los diferentes repositorios indexados se decidió generar un archivo secuencial con registros de longitud variable con el siguiente formato:

\begin{table}[h]
\centering
\begin{tabular}{| c | c | c | c |}
\hline
NumBytes&Repositorio&NumBytes II&Path\\
\hline
uint8\_t & string & uint8\_t & string\\
\hline
\end{tabular}
\caption {Archivo de repositorios}
\end{table}
Este archivo servirá para advertir de la duplicación de nombres de repositorios.\\
\\El campo NumBytes indica cuántos caracteres leer para formar el nombre del repositorio, en tanto que NumBytes II indica la cantidad de caracteres que contiene el Path.\\ Estas cadenas tendrán una longitud máxima de 255 caracteres, lo cual nos parece bastante razonable.\\
\\En el directorio asociado a Path se guardará tanto el archivo que contiene el registro de los documentos indexados como los distintos archivos que conformarán el índice de la colección de documentos, los cuales se analizarán en detalle posteriormente.\\
\\
El archivo de repositorios se guardará en el directorio /home/.datos que se creará al inicio del proceso de indexación en el caso de no existir y luego se actualizará con cada nuevo índice agregado.

\section{Definición del criterio de parseo de los términos}

La estrategia para decidir que se procesa como un término y que caracteres se descartan durante el parseo se detalla a continuación:
\begin{itemize}
\item[•] \textbf{Números:} Los términos constituidos por números no serán incluidos en el listado de términos que conformarán el índice, a excepción de aquellos que puedan resultar importantes en colecciones conteniendo documentos técnicos, como por ejemplo una base de datos de medicina que contenga información sobre vitaminas. Una posible solución para este caso podría ser considerar como términos aquellos que no comiencen con un dígito, por ejemplo, B6 y B12. Otro caso de sumo interés se presenta cuando los términos representan años. Para resolverlo se tendrán en cuenta aquellos términos que posean 4 dígitos, realizando las validaciones correspondientes para cada caso. El resto de los casos serán descartados.

\item[•]\textbf{Signos de puntuación:} Se descartarán todo tipo de signos de puntuación que puedan contener los términos, tales como coma, punto y coma, etc.


\item[•] \textbf{Palabras compuestas:} Se separarán en distintos términos palabras compuestas tales como Bank account, Police department o Fire station. Las palabras que contengan separadores, por ejemplo, MS-DOS, OS/2 o AT\&T se indexarán como un sólo término, al igual que palabras como Bookstore o Homework.

\item[•] \textbf{Separadores:} Se utilizarán como separadores y no se indexarán los siguientes caracteres: ", (, ), —, ', :, ?, ¿, !, ¡. Tampoco se indexarán los caracteres de salto de línea, tabs, etc.

\item[•]\textbf{Capitalización:} Se convertirán los términos que contengan minúsculas en términos conteniendo únicamente mayúsculas. Por lo tanto, se tratará de igual manera a términos como File y file. Una ventaja obvia es evitar la repetición de términos semejantes que contengan los mismos caracteres pero difieran en la capitalización de éstos.

\item[•]\textbf{Stop Words:} Se decidió no descartar ningún tipo de Stop-Words, ya que al no indexar éste tipo de términos se estaría perdiendo precisión en las consultas.

\end{itemize}

\section{Estructura de archivos}

Con el objetivo de crear una aplicación escalable y considerando la posibilidad de que el repositorio a indexar sea lo suficientemente grande, decidimos tomar precauciones en cuanto a las limitaciones físicas del equipo y sobretodo de la memoria principal.


\subsection{Archivos utilizados en el proceso de indexación}

De acuerdo con lo mencionado anteriormente, se decidió construir el índice de a bloques; cada bloque será de un tamaño fijo y representará un buffer que se irá llenando en memoria. En este buffer se guardará el string que representa a un término junto con una lista de los números de documento en los que aparece y por cada documento una lista de posiciones asociada. Una vez lleno el buffer, se ordenará alfabéticamente por término y se agruparán los términos iguales, junto con sus números de documento y posiciones en cada documento. El motivo de ésta decisión es aumentar la velocidad de indexación al no tener que ordenar el buffer cada vez que se agrega un término y luego realizar una búsqueda por cada nuevo término indexado; sólo se ordenará una vez lleno y se recorrerá secuencialmente para actualizar los términos repetidos.\\
Una vez ordenado y actualizado, se mergeará con los bloques anteriores, de existir, y se irán escribiendo y/o actualizando los archivos que representarán el índice del repositorio, a saber:

\subsubsection*{Indice principal}
\begin{table}[h]
\centering
\begin{tabular}{|c|c|}
\hline 
offsetDoc & cantDoc \\
\hline 
uint32\_t & uint16\_t  \\ 
\hline 
\end{tabular} 
\caption{Indice principal del proceso de indexación}
\end{table}

El archivo contendrá registros de longitud fija lo que permitirá en la etapa de consultas realizar un acceso por número de celda. La ventaja de ésto será realizar un solo acceso a este archivo para obtener el registro buscado, como se explicará más adelante.\\
\\El primer campo contendrá el offset al inicio de la lista de documentos del término; mientras que el restante almacenará la cantidad de documentos en los que aparece el término.
Los términos serán comprimidos utilizando \textbf{Front Coding} y se almacenarán concatenados en el siguiente archivo:

\subsubsection*{Lista de términos}

Este archivo tendrá registros de longitud variable y será donde se almacenará el léxico del índice. Cada registro contendrá la cantidad de caracteres repetidos con respecto al término anterior, la cantidad de caracteres distintos y dichos caracteres.\\
\\
El formato del archivo será el siguiente:\\
\begin{table}[h]
\centering
% centering table
\begin{tabular}{| c | c | c |}
\hline
Repetidos&Distintos&Caracteres\\
\hline
uint8\_t & uint8\_t & string\\
\hline
\end{tabular}
\caption{Lista de términos}
\end{table}\\
El último campo contendrá únicamente los caracteres que no se repiten con respecto al término anterior.
Al iniciar el proceso de consulta, se cargará este archivo en un vector en memoria descomprimiendo los términos y se realizará una búsqueda teniendo en cuenta que se encuentra ordenado alfabéticamente por término. Hemos diseñado ésta estrategia ya que creemos que el recorrido secuencial de la lista de términos no será costoso; y de ésta manera estamos evitando los accesos al índice principal que requeriría una búsqueda binaria y además se ahorra el espacio del offset a la lista de términos en el índice principal. De ésta manera sólo se realizará un acceso al índice principal por cada término de la consulta.

\subsubsection*{Lista de documentos}

Este archivo contendrá los documentos en los cuales aparecen los términos del índice, junto con la frecuencia del término en cada documento y un offset a la lista de posiciones para el documento. Para cada término se almacenará el primer documento y luego la distancia al documento anterior, formando una lista de distancias.\\
\\El formato de registro para cada documento de un término será el siguiente:\\

\begin{table}[h]
\centering
\begin{tabular}{|c|c|c|}
\hline 
NroDocumento & frecuencia & offsetPosiciones \\ 
\hline 
\end{tabular} 
\caption{Lista de documentos}
\end{table}

Este archivo se comprimirá utilizando \textbf{Código} \textbf{Gamma} para el NroDocumento y frecuencia; y \textbf{Código} \textbf{Delta} para el campo offsetPosiciones. Las razones de ésta elección serán expuestas más adelante.\\ 
\\Al final de la lista de documentos de cada término, se rellenará el resto del último byte, de ser necesario,  para que el offset del índice principal pueda tener la referencia a nivel de byte.

\subsubsection*{Lista de posiciones}

Este archivo contendrá las posiciones asociadas a cada documento para los términos contenidos en el índice principal. Se comprimirá utilizando \textbf{Código Delta} por las razones expuestas en el apartado Pruebas realizadas y se codificará para cada lista la primer posición y luego, para cada posición, la distancia a la posición anterior. Una vez finalizada la escritura de una lista, se rellenará el último byte de la lista, de ser necesario, debido a  lo mencionado anteriormente.


\section{Construcción del índice}

La etapa de construcción del índice consistirá en los siguientes pasos:

\begin{enumerate}

	\item \textbf{Lectura de documentos en el repositorio: }\\Procesamiento secuencial de documentos que se encuentran en el repositorio. Al iniciarse esta operación se inicializará el identificador de documentos en 0 y se incrementará cada vez que se lea uno nuevo.

	\item \textbf{Obtención de los términos en un documento: }\\ Por cada documento procesado se obtendrán los términos teniendo en cuenta las consideraciones definidas en el criterio de parseo de los términos.
		
	\item \textbf{Almacenamiento de términos junto con sus documentos y posiciones asociadas: }\\
	Cada término se almacenará en el buffer en memoria junto con el documento donde aparece y su respectiva posición.

		\item \textbf{Agrupación de términos: }Una vez llenado el buffer, se realiza un recorrido secuencial del mismo para agrupar términos iguales actualizando sus listas de documentos y posiciones.
		
		\item \textbf{Generación de los archivos del índice:}
		\\Al llenarse por primera vez el buffer se crean los archivos que representan el índice, al momento de recorrer el buffer secuencialmente para agrupar términos. Es decir, una vez encontrado un término distinto en el proceso de agrupamiento, se almacenan en el índice los datos correspondientes al término anteriormente procesado. Todas las operaciones de escritura en los archivos se realizan de forma secuencial.
Por cada término procesado en el buffer se efectúan los siguientes pasos:

		\begin{enumerate}
		\item Se almacena el término en el archivo que contiene el léxico como también en memoria para poder completar los campos repetidos y distintos del próximo término.

		\item Se obtiene la lista de documentos del término y se almacena en memoria el número de documento actual para ir generando una lista de distancias cuando se lean los siguientes documentos. Para cada documento, se escribe un registro en el archivo que contiene la lista de documentos con el número de documento actual o distancia al anterior, su frecuencia, que será el tamaño de la lista de posiciones; y el offset actual al archivo que almacenará las posiciones. 
		
		\item Luego se obtiene la lista de posiciones asociada al documento y se escriben en el archivo correspondiente las posiciones concatenadas.
		
		\item Al terminar de escribir las posiciones, se rellena el último byte del último registro escrito, de ser necesario, para poder mantener el campo que almacena el offset a este archivo siempre con respecto al inicio de 1 byte.

		\end{enumerate}
		
		\item \textbf{Etapa de Merge:}\\Al llenarse un nuevo bloque en memoria, se realiza un merge entre el bloque actual y el índice actual. En cada proceso de Merge los archivos del índice son destruidos y se crean nuevos archivos actualizados. En esta operación sólo se recorrerá secuencialmente una vez el índice y se escribirá  también de manera secuencial cada archivo actualizado con las novedades del bloque actual siguiendo los pasos mencionados en el item anterior.
		\item Una vez terminado el proceso, se guardarán los archivos finales del índice en un directorio creado con el nombre del índice en la carpeta /home/.datos
\end{enumerate}
	

\section{Resolución de consultas}

Esta etapa consistirá en los siguientes pasos:

\begin{enumerate}


\item \textbf{Parseo de la consulta: }\\Se parsea la lista de términos de la consulta con los mismos criterios utilizados en la etapa de indexación.

\item \textbf{Búsqueda de términos: }\\Para cada término se realiza una búsqueda con los términos que se encuentran en memoria. Si el término no es encontrado, el resultado de la consulta será nulo.
En caso contrario, se accede al índice principal mediante el número de celda que corresponderá a la posición del término en el vector en memoria y se obtiene el registro asociado al término.

\item \textbf{Obtención de los documentos asociados a los términos: }\\Una vez encontrado el registro en el índice principal, se obtiene la cantidad de documentos en los que aparece el término y el offset a la lista de documentos. Se accede a este archivo mediante dicho offset, se leen tantos registros como indique la cantidad de documentos y se almacenan estos datos en memoria; formándose para cada término una lista de documentos y para cada documento, una lista de posiciones asociada. Este proceso se repite para cada término de la consulta y una vez finalizado, se realiza una intersección entre las listas de documentos de cada término. De no haber intersección se termina la consulta. El motivo de realizar la lectura de las posiciones con anterioridad a la intersección es el de reducir accesos aleatorios a disco innecesariamente, ya que en este caso todos los accesos a disco serán secuenciales.

\item \textbf{Normalización de posiciones e intersección de las mismas:}\\ Luego de realizada la intersección entre los documentos de los términos de la consulta, se normalizarán las listas de posiciones de cada documento según las posiciones de cada término en la consulta y se realizará una intersección entre estas listas normalizadas que arrojará el resultado de la consulta.

\item \textbf{Obtención de los nombres de los documentos resultantes: }\\Al obtener los números de documentos en los cuales aparece la palabra o frase buscada, se accederá al índice del archivo que contiene la información de los documentos indexados, por número de celda; el cual coincide en este caso con el número de documento; y se recuperará el nombre del documento para cada documento resultado.
\end{enumerate}

\section{Pruebas realizadas}

Para decidir que método de compresión utilizar en la lista de documentos y posiciones se programaron dos métodos distintos de codificación: \textbf{Gamma} y \textbf{Delta}.


\subsection*{Códigos de compresión}

Se codificaron 1 millón de longitudes y se completaron bytes emulando la terminación de una lista cada 100 longitudes.\\

 Los resultados fueron los siguientes:
\bigskip
\begin{table}[h]
\centering
\begin{tabular}{|c|c|c|}
\hline 
Longitud & Gamma & Delta \\ 
\hline 
10 & 0,88 MB & 1 MB \\ 
\hline 
25 & 1,1 MB & 1,1 MB \\ 
\hline 
50 & 1,4 MB & 1,3 MB \\ 
\hline 
100 & 1,6 MB & 1,4 MB \\ 
\hline 
1000 & 2,4 MB & 2 MB \\ 
\hline 
10000 & 3,4 MB & 2,5 MB \\ 
\hline 
100000 & 4,1 MB & 3,1 MB \\ 
\hline 
1000000 & 4,9 MB & 3,5 MB \\ 
\hline 
\end{tabular} 
\caption{Comparación entre Código Gamma y Delta}
\end{table}

\begin{figure}[h]
\centering
\includegraphics[scale=0.5]{gammavsdelta}
\caption{Comparación entre Código Gamma y Delta}
\end{figure}


Podemos concluir entonces que el Código Gamma es superior para longitudes menores a 25 y luego el Código Delta es muy superior; sobretodo a medida que vamos creciendo en la longitud de los códigos.
\newpage
Las decisiones tomadas en cuanto a que código usar para cada lista están basadas en éstos resultados.\\
El archivo que contiene las posiciones será el de mayor tamaño (MB) que se generará en el proceso de indexación. Pudimos comprobar que este archivo ocupará alrededor de un 20\% del tamaño total del repositorio a indexar.\\
\\ Las pruebas son las siguientes :\\
\begin{table}[h]
\centering
\begin{tabular}{|c|c|}
\hline
Tamaño del repositorio & Tamaño de la lista de posiciones \\
\hline
10 MB. & 2,8 MB\\
\hline
50 MB & 12 MB\\
\hline
100 MB & 27 MB\\
\hline
\end{tabular}
\caption{Tamaño del repositorio vs. tamaño de la lista de posiciones}
\end{table}

\newpage
\begin{thebibliography}{99}
\bibitem{HB98} Elias gamma coding. \url{http://en.wikipedia.org/wiki/Elias_gamma_coding}
\bibitem{HB98} Elias delta coding. \url{http://en.wikipedia.org/wiki/Elias_delta_coding}
\bibitem{HB98} Motor de búsqueda en java. \url{http://lucene.apache.org/core/}
\bibitem{HB98} Apunte de indexación de la materia Organización de datos.  \url{http://ar.groups.yahoo.com/group/datos/files/Apuntes/Information Retrieval/indices.pdf}
\bibitem{HB98} Index Compression for Information Retrieval Systems.  	\url{http://www.dc.fi.udc.es/~roi/publications/rblanco-phd.pdf}
\end{thebibliography}
\end{document}